#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/11/28 13:55
# @USER    : Shengji He
# @File    : ReversePairs.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List
import bisect


class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        """
        Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

        You need to return the number of important reverse pairs in the given array.

        Example1:
            Input: [1,3,2,3,1]
            Output: 2
        Example2:
            Input: [2,4,3,5,1]
            Output: 3
        Note:
            1. The length of the given array will not exceed 50,000.
            2. All the numbers in the input array are in the range of 32-bit integer.

        :param nums:
        :return:
        """
        tb, res = [], 0
        for n in reversed(nums):
            res += bisect.bisect_left(tb, n)
            n2 = 2 * n
            idx = bisect.bisect_left(tb, n2)
            tb.insert(idx, n2)
        return res


if __name__ == '__main__':
    nums = [1, 3, 2, 3, 1]
    S = Solution()
    print(S.reversePairs(nums))
    print('done')
